1. 题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2： 输入: "cbbd" 输出: "bb"

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

Manacher算法

3. 代码

将预处理后的字符串从1开始计数了，习惯使然

class Solution {
public:
    string Manacher(string s){
        string newstr;
        int len = s.size(), nlen = 2*s.size()+1, res = 1, resp = 0;
        newstr.resize(nlen);
        for(int i=1;i<=len;++i) newstr[2*i-1]='#',newstr[2*i]=s[i-1];
        newstr[nlen]='#';

        int pos=0,R=0;
        int p[nlen+1];
        for(int i=1;i<=nlen;++i){
            if(i<R) p[i] = min(p[2*pos-i],R-i);
            else p[i]=1;
            while(i-p[i]>=1&&i+p[i]<=nlen&&newstr[i-p[i]]==newstr[i+p[i]]) p[i]++;
            if(i+p[i]>R) R=i+p[i],pos=i;
            //res：原字符串最长回文子串长度
            //resp：原字符串最长回文子串 中心位置 ，偶数长度的为靠右位置
            if(p[i]-1>res) res = p[i]-1, resp = (i-1)/2;
        } 
        return s.substr(resp-res/2,res);
    }
    string longestPalindrome(string s) {
        return Manacher(s);
    }
};